/*
 *  This file implements the malloc() and free() functions to allocate dynamic memory.
 */


/*
  TO DO:
  Make this code reentrant... ie add spinlocks to public variables

 */

#include <malloc.h>
#include <klib.h>


#define PAGE_SIZE 4096

struct mem_block_t
{
  dword_t base;
  long size;
  long gap;
  struct mem_block_t *next;
};


/* pointer to the first block */
struct mem_block_t *first=NULL,*last=NULL;
/* pointer to the start of the free store (heap) */
dword_t freestore=0,newspace=0,freespace=0;
// free space counter
long free_space_left=0;


/*
 * internal prototypes
 */

// on success, returns a pointer to the new area (page), doesn't accept negative offsets
extern void *morecore(long increment);


/* 
 * public functions 
 */

void *malloc(size_t size)
  {
    struct mem_block_t *mbs,*mb,*best;
    size_t req;
    int npages;

    //printf("Requesting chunk of %d bytes.\n",size);

    req=size+sizeof(struct mem_block_t);

    // look for any big enough gap inbetween blocks
    // use the best fit algorithm    
    best=NULL;
    //if (first!=NULL)
      //for (mb=first;mb->next!=NULL;mb=mb->next)
      for (mb=first;mb!=NULL;mb=mb->next)
	if (mb->gap >= req)	    
	  if (best==NULL || mb->gap < best->gap)
	    best=mb;
    

    // if we didn't find any free space between previously allocated blocks, we'll check at the end of the list for how much free space is left, if none we'll request some more
    if (best==NULL && req>free_space_left)
      {
	// we need some more memory pages, it seems.
	// determine how many new pages we need
	npages = req / PAGE_SIZE;
	if (req % PAGE_SIZE)
	  npages++;

	// allocate them
	newspace=(dword_t)morecore(npages*PAGE_SIZE);
	free_space_left += PAGE_SIZE * npages;

	// it's the initialization (first time ever we execute malloc)
	if (freestore==0)
	  {
	    freestore=freespace=newspace;
	    first=(struct mem_block_t *)freestore;
	  }
      }


    if (best==NULL)
      {    
	// Allocation occours at the end of the list
	// allocate a memory block structure to keep track of the allocation
	mbs=(struct mem_block_t *)freespace;
	// fill in structure
	mbs->base = freespace + sizeof(struct mem_block_t);
	mbs->size = size;
	mbs->gap = 0; // it's the last node... we don't need this info here
	mbs->next = NULL;
	// pointer to previously allocated block
	if (last!=NULL)
	  last->next = mbs;
	// now the current one has become the last allocated one
	last = mbs;
	// update the free space pointer and counter
	freespace += req;
	free_space_left -= req;
      }
    else
      {
	//Alocation occours in the middle of the list (a gap was found)
	if (first==best && best->size==0) //it's a dummy block (reuse it)
	  {
	    // the block had been initialized when it was used... 
	    // we only need to update a few fields
	    mbs=best;
	    mbs->size = size;
	    mbs->gap -= size;  // take all the room you need	    
	  }
	else
	  {   
	    // it's a normal block
	    mbs=(struct mem_block_t *)(best->base + best->size);
	    // fill in structure
	    mbs->base = best->base + best->size + sizeof(struct mem_block_t);
	    mbs->size = size;
	    mbs->gap = best->gap - req;  // now we do update this information
	    mbs->next = best->next;
	    best->next = mbs;
	    best->gap=0;
	  }
      }
      
    return (void *)(mbs->base);
  }


void free(void *ptr)
  {
    struct mem_block_t *mb,*found,*prev;

    //printf("Freeing: %x\n",(dword_t)ptr);
    //printf("   --> Last: %x\n",(dword_t)last);

    // if ptr is NULL do nothing (standard behavior)
    if (ptr==NULL)
      return;

    if (first==NULL)      
      {
	printf("Warning: about address %x\n",(dword_t)ptr);
	panic("trying to free unallocated memory block.\n");
      }

    // look for the block to free
    found=prev=NULL;

    /*
    if (first!=NULL)      
      {
    */
	//for (mb=first;mb->next!=NULL;mb=mb->next)
	for (mb=first;mb!=NULL;mb=mb->next)
	  if (mb->base == (dword_t)ptr)
	    {
	      found=mb;
	      break;
	    }
	  else
	    prev=mb;
	/*
      }
    else 
      //maybe we should panic here... (kernel is trying to free non allocated memory block)
      return;
	*/
    // change it in:
    /*
    if (found==NULL)
      panic(...);
     */

	/*
    printf("   --> Found: %x\n",(dword_t)found);
    printf("   --> Prev:  %x\n",(dword_t)prev);
    printf("   --> Last:  %x\n",(dword_t)last);
	*/
    

    // if it's the last block (includes the case it's the only one block present) we must release the memory to the remaining part of the free store
    if (last==found)
      {
	// decrease the free space pointer
	freespace -= found->size + sizeof(struct mem_block_t);
	// increase the free memory count
	free_space_left += found->size + sizeof(struct mem_block_t);

	// set the new end of the list	
	if (prev!=NULL) // it's not the first one too
	  {
	    prev->next = NULL;
	    last=prev;
	  }
	else
	  {
	    // it is the first one too...
	    first=NULL;
	    last=NULL;  
	  }
      }
    else
      {
	// it's not the last one... we may create gaps
	// note, it may still be the first one

	/* if it's the first one we need to create a "dummy" block, with size set to zero 
	 * and gap set to the previous size.
	 * If malloc() finds such a block, it will use it for allocation, if it's appropriate.
	 */
	if (first==found)
	  {
	    // it's the first one... turn it into a dummy block
	    //found->gap += found->size + sizeof(struct mem_block_t);
	    found->gap += found->size;
	    found->size = 0;	    
	  }
	else // it's in the middle of the list
	  {
	    prev->gap += found->size + sizeof(struct mem_block_t);
	    prev->next = found->next;	    
	  }
      }   

    /*
    // list is empty?
    // This created a NULL warning... trying to free unallocated block...
    if (first!=NULL && first->size==0 && first==last)
      {
	// decrease the free space pointer
	freespace -= first->gap + sizeof(struct mem_block_t);
	// increase the free memory count
	free_space_left += first->gap + sizeof(struct mem_block_t);

	first=NULL;
	last=NULL;
      }
    */
  }

void print_allocations()
  {
    struct mem_block_t *mb;

    printf("  ***Last:  %x\n",(dword_t)last);
    printf("Address   Start     Size      Gap       Next\n");
    
    if (first!=NULL)
      for (mb=first;mb!=NULL;mb=mb->next)
	printf("%x  %x  %d         %d         %x\n",mb,mb->base,mb->size,mb->gap,mb->next);

  }
